
//2563.统计公平数对的数目
class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        int n=nums.size();
        sort(nums.begin(),nums.end());  //先进行排序，此时的left和right有序方便对不需要组合进行剪枝
        int left=0,right=n-1;
        long long ans=0;
        while(left<right)
        {
            if(nums[left]+nums[right]>upper) right--;  //当left+right对应的值大于upper时right就没有匹配的left了
            else if(nums[left]+nums[right]<lower) left++;  //当left+right对应的值小于lower时left就没有匹配的right了
            else
            {
                //此时的nums[left]+nums[right]是满足题意的，所以可以固定right，将找第一个left不满足条件的位置
                int end=upper_bound(nums.begin()+left,nums.begin()+right,upper-nums[right])-nums.begin()
                                    -left;
                ans+=end;
                right--;
            }
        }
        return ans;
    }
};